package algorithms.leaning.class12;

import common.bean.TreeNode;

/**
 * 判断二叉树是否是搜索二叉树
 * 每棵子树的左树比头小，右树比头大
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code3_二叉树_搜索二叉树 {
    // 1、左树是搜索二叉树，右树是搜索二叉树
    // 2、左树最大值小于当前节点、右树最小值大于当前节点

    public static boolean isBST(TreeNode node) {
        return process(node).bst;
    }


    private static Info process(TreeNode node) {
        if (node == null) {
            // 不得影响左右子树的比较
            return new Info(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        Info tl = process(node.left);
        Info tr = process(node.right);
        boolean search = tl.bst && tr.bst && tl.max < node.val && tr.min > node.val;
        int min = Math.min(Math.min(tl.min, tr.min), node.val);
        int max = Math.max(Math.max(tl.max, tr.max), node.val);
        return new Info(search, min, max);
    }

    private static class Info {
        boolean bst; // 是否搜索二叉树
        int min; // 最小值
        int max; // 最大值

        public Info(boolean search, int min, int max) {
            this.bst = search;
            this.min = min;
            this.max = max;
        }
    }

}